﻿namespace ProblemsSet
{
    public class Problem_149 : BaseProblem
    {
        public override object GetResult()
        {
            const int max = 2000;
            //const int max = 4;

            BigInteger res = 0;

            var test = new []
                           {
                               new BigInteger[] {-2, 5, 3, 2},
                               new BigInteger[] {9, -6, 5, 1},
                               new BigInteger[] {3, 2, 7, 3},
                               new BigInteger[] {-1, 8, -4, 8},
                           };

            var real = MathLogic.GetFibonacciSeq(max);
            //var real = test;

            for (var i = 0; i < max; i++)
            {
                var tmp = FindMax(ref real, max, 0, i, 1, 0);
                if (tmp > res)
                    res = tmp;

                tmp = FindMax(ref real, max, 0, i, 1, 1);
                if (tmp > res)
                    res = tmp;

                tmp = FindMax(ref real, max, i, 0, 0, 1);
                if (tmp > res)
                    res = tmp;

                tmp = FindMax(ref real, max, i, 0, 1, 1);
                if (tmp > res)
                    res = tmp;

                tmp = FindMax(ref real, max, i, 0, -1, 1);
                if (tmp > res)
                    res = tmp;

                tmp = FindMax(ref real, max, max-1, i, -1, -1);
                if (tmp > res)
                    res = tmp;
            }

            return res;

        }

        private BigInteger FindMax(ref BigInteger[][] mas, long max, int x, int y, int stepX, int stepY)
        {
            BigInteger ver = 0;
            
            BigInteger maxVer = 0;
            BigInteger verMinus = 0;
            bool fromMinus = false;

            for (int i = 0; i <= max; i++)
            {
                int curX = x + i * stepX;
                int curY = y + i * stepY;

                if (curY < 0 || curY >= max)
                    break;

                if (curX < 0 || curX >= max)
                    break;

                if (mas[curX][curY] < 0)
                {
                    verMinus += mas[curX][curY];
                    fromMinus = true;
                }
                else
                {
                    maxVer = maxVer > ver ? maxVer : ver;

                    if (verMinus + ver <= 0)
                    {
                        ver = 0;
                    }
                    else
                    {
                        if (fromMinus)
                            ver += verMinus;
                    }
                    fromMinus = false;
                    verMinus = 0;
                    ver += mas[curX][curY];
                    maxVer = maxVer > ver ? maxVer : ver;
                }
            }

            return maxVer;
        }

        
        public override string Problem
        {
            get
            {
                return @"Looking at the table below, it is easy to verify that the maximum possible sum of adjacent numbers in any direction (horizontal, vertical, diagonal or anti-diagonal) is 16 (= 8 + 7 + 1).

2	5	3	2
9	6	5	1
3	2	7	3
1	8	4	  8
Now, let us repeat the search, but on a much larger scale:

First, generate four million pseudo-random numbers using a specific form of what is known as a 'Lagged Fibonacci Generator':

For 1  k  55, sk = [100003  200003k + 300007k3] (modulo 1000000)  500000.
For 56  k  4000000, sk = [sk24 + sk55 + 1000000] (modulo 1000000)  500000.

Thus, s10 = 393027 and s100 = 86613.

The terms of s are then arranged in a 20002000 table, using the first 2000 numbers to fill the first row (sequentially), the next 2000 numbers to fill the second row, and so on.

Finally, find the greatest sum of (any number of) adjacent entries in any direction (horizontal, vertical, diagonal or anti-diagonal).";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 52852124;
            }
        }
    }
}
